#include <cstdio>//uncle-lu
#include <algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

const int INF = 1e5+10;

struct node{
	int x, y;
	int val_1, val_2;
	int visit;
	int sit;
};

node edge[INF*2];
int n, k, m;
int Father[INF];

bool cmp_1(node a, node b)
{
	return a.val_1 < b.val_1;
}

bool cmp_2(node a, node b)
{
	return a.val_2<b.val_2;
}

bool cmp_3(node a, node b)
{
	return a.sit < b.sit;
}

int Find_Father(int x)
{
	return Father[x] == x ? x : Father[x] = Find_Father(Father[x]);
}

int main()
{
	read(n); read(k); read(m);
	m--;
	for(int i=1; i<=m; ++i)
	{
		read(edge[i].x); read(edge[i].y); read(edge[i].val_1); read(edge[i].val_2);
		edge[i].sit = i;
		Father[i] = i;
	}
	
	std::sort(edge+1,edge+1+m, cmp_1);
	int cnt = 0 , ans = 0;
	for(int i=1; i<=m;++i)
	{
		int xx = Find_Father(edge[i].x) , yy = Find_Father(edge[i].y);
		if(xx != yy)
		{
			Father[yy] = xx;
			edge[i].visit = 1;
			ans = std::max(ans, edge[i].val_1);
			cnt++;
		}
		if(cnt == k)break;
	}

	std::sort(edge+1,edge+1+m, cmp_2);
	for(int i=1;i<=m;++i)
	{
		if(edge[i].visit)continue;
		int xx = Find_Father(edge[i].x) , yy = Find_Father(edge[i].y);
		if(xx != yy)
		{
			Father[yy] = xx;
			edge[i].visit = 2;
			ans = std::max(ans,edge[i].val_2);
			cnt++;
		}
		if(cnt == n-1)break;
	}

	std::sort(edge+1,edge+1+m, cmp_3);
	printf("%d\n",ans);
	for(int i=1;i<=m;++i)
	{
		if(edge[i].visit)
			printf("%d %d\n",edge[i].sit,edge[i].visit);
	}
	return 0;
}
